package com.itheima.datastructure.binarysearchtree;

import com.itheima.datastructure.binarysearchtree.binarytree.TreeNode;

//根据前序遍历实现二叉搜索树
public class E06Leetcode1008 {
    //常规递归 时间复杂的O(n*log(n))
    public TreeNode bstFromPreorder1(int [] preorder){
        TreeNode root=new TreeNode(preorder[0]);//创建根节点
        for(int i=1;i<preorder.length;i++){
            int val=preorder[i];
            insert1(root,val);
        }
        return root;
    }
    //插入操作
    private TreeNode insert1(TreeNode node,int val){
        //找到了合适的空位就要插入
        if(node==null){
            return new TreeNode(val);
        }
        //建立二叉树大小关系
        if(val<node.val){
            node.left=insert1(node.left,val);
        }else if(node.val<val){
            node.right=insert1(node.right,val);
        }
        return node;
    }


    //利用上下界卡位递归
    public TreeNode bstFromPreorder2(int[] preorder){
        return insert2(preorder,Integer.MIN_VALUE);
    }

    int i=0;
    private TreeNode insert2(int[] preorder,int max){
        if(i==preorder.length){ //如果计数器与数组长度相同，代表遍历结束
            return null;
        }
        int val=preorder[i];
        //代表遍历到的值的大于父节点的上界，不能插入，父节点给他null子节点
        if(val>max){
            return null;
        }
        //反之就创建新节点
        TreeNode node=new TreeNode(val);
        i++;//计数器记录
        node.left=insert2(preorder,val);
        node.right=insert2(preorder,max);
        return node;
    }

    //分治法，分而治之
    public TreeNode bstFromPreorder3(int [] preorder){
          return partition(preorder,0,preorder.length-1);
    }
    private TreeNode partition(int[] preorder,int start,int end){
        //start表示根节点；end表示子树的最后一个节点
        if(start>end){
            return null;
        }
        TreeNode root=new TreeNode(preorder[start]);
        //index表示右子树的第一个节点
        int index=start+1;
        while(index<=end){
            if(preorder[index]>preorder[end]){
                break;
            }
            index++;
        }
        //index就是右子树的起点
        root.left=partition(preorder,start+1,index-1);
        root.right=partition(preorder,index,end);
        return root;
    }


}
